package binarysearch;

import org.junit.Test;

public class MySqrt69 {

    @Test
    public void test() {
        int x = 2147395599; // overflow
        System.out.println(Integer.MAX_VALUE); // 2147483647
        System.out.println(mySqrtWithLong(x));
        System.out.println(mySqrtByDivision(x));
        System.out.println(mySqrtByDivision(0));
        System.out.println(mySqrtByDivision(1));
    }

    // 关于返回值:
    // 第一种方案, 返回left之前, 要判断是否 x/left < left. 如果是, left要减1. 因为left在最后一次循环中可能变大了.
    // 第二种方案, 直接返回right即可. 因为最后一次循环中, right至少是减小或没变, 不会增大.

    // rightBound
    public int mySqrtWithLong(int x) {
        System.out.println("-------------------");
        long left = 0;
        long right = x;
        while (left <= right) {
            // use long to avoid overflow
            long mid = left + (right - left) / 2;
            System.out.format("x: %d, L: %d, R: %d, M: %d\n", x, left, right, mid);
            // use long to avoid overflow
            long mid2 = mid * mid;
            if (mid2 > x) {
                right = mid - 1;
            } else if (mid2 < x) {
                left = mid + 1;
            } else {
                return (int)mid;
            }
        }
        return (int)right;
    }

    // rightBound
    public int mySqrtByDivision(int x) {
        System.out.println("-------------------");
        // avoid divided by 0 when x=0
        // avoid mid=0 when x=1
        if (x <= 1) {
            return x;
        }
        int left = 0;
        int right = x;
        while (left <= right) {
            // use long to avoid overflow
            long mid = left + (right - left) / 2;
            System.out.format("x: %d, L: %d, R: %d, M: %d\n", x, left, right, mid);
            // use division
            int temp = x/(int)mid;
            if (temp < mid) {
                right = (int)mid - 1;
            } else if (temp > mid) {
                left = (int)mid + 1;
            } else {
                return (int)mid;
            }
        }
        return right;
    }
}
